package com.leetcode.程序员面试金典.medium;

import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2021-06-20 11:49
 */
public class 面试题_17_23_最大黑方阵 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[][] matrix = {
        {1, 0, 1},
        {0, 0, 1},
        {0, 0, 1}
    };

    int[][] matrix2 = {
        {0, 1, 1},
        {1, 0, 1},
        {1, 1, 0}
    };

    int[][] matrix3 = {{1, 1, 1, 0, 1, 1, 0, 1, 0, 0}, {0, 1, 0, 1, 1, 0, 0, 0, 1, 1},
        {0, 0, 1, 1, 0, 0, 1, 1, 1, 0}, {0, 1, 1, 1, 0, 1, 0, 0, 1, 0},
        {1, 1, 0, 1, 1, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 1, 1, 0},
        {1, 0, 0, 0, 0, 1, 1, 1, 1, 1}, {1, 0, 1, 0, 1, 0, 0, 0, 1, 0},
        {1, 1, 1, 1, 0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 0}};

    int[] square = solution.findSquare(matrix3);

    System.out.println("======================================");

    System.out.println(Arrays.toString(square));
  }

  public static void print2Arr(int[][] arr) {
    for (int[] a : arr) {
      System.out.println(Arrays.toString(a));
    }
  }

  static
  class Solution {

    public int[] findSquare(int[][] matrix) {

      if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
        return new int[0];
      }

      // 计算每个黑像素向下和向左的延伸
      int[][] downSizeArr = new int[matrix.length][matrix.length];
      int[][] rightSizeArr = new int[matrix.length][matrix.length];

      int maxIndex = matrix.length - 1;

      downSizeArr[maxIndex][maxIndex] = matrix[maxIndex][maxIndex] == 0 ? 1 : 0;
      rightSizeArr[maxIndex][maxIndex] = matrix[maxIndex][maxIndex] == 0 ? 1 : 0;

      // 最右边一列的 downSizeArr
      for (int i = maxIndex - 1; i >= 0; --i) {
        downSizeArr[i][maxIndex] = matrix[i][maxIndex] == 0 ? downSizeArr[i + 1][maxIndex] + 1 : 0;
        rightSizeArr[i][maxIndex] = matrix[i][maxIndex] == 0 ? 1 : 0;
      }

      // 最下边一行的 rightSizeArr
      for (int j = maxIndex - 1; j >= 0; --j) {
        rightSizeArr[maxIndex][j] =
            matrix[maxIndex][j] == 0 ? rightSizeArr[maxIndex][j + 1] + 1 : 0;
        downSizeArr[maxIndex][j] = matrix[maxIndex][j] == 0 ? 1 : 0;
      }

      // 计算整个方阵的 downSizeArr 和 rightSizeArr
      for (int i = maxIndex - 1; i >= 0; --i) {
        for (int j = maxIndex - 1; j >= 0; --j) {
          downSizeArr[i][j] = matrix[i][j] == 0 ? downSizeArr[i + 1][j] + 1 : 0;
          rightSizeArr[i][j] = matrix[i][j] == 0 ? rightSizeArr[i][j + 1] + 1 : 0;
        }
      }

//      System.out.println("=========matrix============");
//      print2Arr(matrix);
//      System.out.println("=========downSizeArr============");
//      print2Arr(downSizeArr);
//      System.out.println("============rightSizeArr========");
//      print2Arr(rightSizeArr);

      int[] result = new int[3];

      // 找到符合条件的结果
      for (int i = 0; i < matrix.length; ++i) {
        for (int j = 0; j < matrix.length; ++j) {
          if (matrix[i][j] == 0) {
            int downSize = downSizeArr[i][j];
            int rightSize = rightSizeArr[i][j];
            int minSize = Integer.min(downSize, rightSize);
            if (minSize == 1 && result[2] == 0) {
              // 只有当前点是黑像素
              result[0] = i;
              result[1] = j;
              result[2] = minSize;
            } else if (minSize > result[2]) {
              // 找到符合条件的最大边长
              for (int size = minSize; size > result[2]; --size) {
                int index = size - 1;
                downSize = downSizeArr[i][j + index];
                rightSize = rightSizeArr[i + index][j];
                minSize = Integer.min(downSize, rightSize);
                if (minSize >= size) {
                  result[0] = i;
                  result[1] = j;
                  result[2] = size;
                  break;
                }
              }
            }
          }
        }
      }

      if (result[2] == 0) {
        return new int[0];
      }

      return result;
    }
  }

}
